package cn.pugle.oj.base;

import java.util.ArrayList;
import java.util.LinkedHashMap;

/**
 * 递归
 * 双指针循环
 * 找左确界
 * https://labuladong.gitbook.io/algo/di-ling-zhang-bi-du-xi-lie/er-fen-cha-zhao-xiang-jie#er-xun-zhao-zuo-ce-bian-jie-de-er-fen-sou-suo
 * <p>
 * 标准二分查找, {@link java.util.Arrays#binarySearch0(int[], int, int, int)}
 * <p>
 * 如果死循环了, 注意是不是移动lr=m的时候没有±1
 *
 * @author tzp
 * @since 2020/10/19
 */
public class BinarySearch {

    public static int upper_bound_(int n, int v, int[] a) {
        if (a.length == 0) return -1;
        int left = 0;
        int right = a.length; // fixme 注意

        while (left < right) { // fixme 注意
            int mid = (left + right) / 2;
            if (a[mid] == v) {
                right = mid;
            } else if (a[mid] < v) {
                left = mid + 1; // fixme 注意
            } else if (a[mid] > v) {
                right = mid; // fixme 注意
            }
        }
        // fixme 注意
        // 有些时候最后要检查l/r越界的情况
        // if (right < 0 || nums[right] != target)
        //   return -1;
        return left;
    }

    public static void main(String[] args) {
        System.out.println(upper_bound_(100, 100, new int[]{2, 3, 3, 4, 4, 5, 5, 5, 6, 6, 7, 7, 9, 9, 9, 10, 10, 12, 14, 16, 17, 18, 18, 18, 19, 22, 23, 23, 26, 26, 26, 26, 28, 28, 29, 29, 29, 32, 33, 35, 36, 38, 39, 39, 40, 41, 46, 47, 47, 47, 49, 50, 54, 55, 55, 55, 56, 57, 57, 58, 58, 58, 59, 61, 61, 62, 62, 62, 62, 63, 63, 67, 67, 69, 70, 70, 71, 72, 74, 75, 76, 79, 84, 85, 85, 86, 89, 92, 93, 93, 93, 94, 94, 95, 97, 97, 97, 97, 97, 99}));
    }
}
